We propose and study a new class of submodular functions called deep submodular functions (DSFs). We define DSFs and situate them within the broader context of classes of submodular functions in relationship both to various matroid ranks and sums of concave composed with modular functions (SCMs). Notably, we find that DSFs constitute a strictly broader class than SCMs, thus motivating their use, but that they do not comprise all submodular functions. Interestingly, some DSFs can be seen as special cases of certain deep neural networks (DNNs), hence the name. Finally, we provide a method to learn DSFs in a max-margin framework, and offer preliminary results applying this both to synthetic and real-world data instances.

Problem definition - The paper proposes a new family of submodular functions called deep submodular functions. They are defined similar to a neural network where there are many nodes in each level. At each node you take a positive linear combination of previous layer and then apply a concave function. Contributions - The main important contribution of the paper is proposing the family of DSF and showing applications to text summarization. They show that DSF's generalize all of them except cycle matroid rank.